#include <iostream>
using namespace std;

static int partitionStart[15];      // 起始地址数组 空闲分区编号就简单0-9
static int partitionSize[15];       // 分区的大小
static bool partitionAllocated[15]; // 是否被占用 否false
static int numFreePartitions;       // 首次适应算法，空闲分区以地址递增形式链接，分配内存顺序寻找，找到大小首个满足的空闲分区

void init()
{
    partitionStart[0] = 0;

    partitionSize[0] = 128;

    partitionAllocated[0] = false;

    numFreePartitions = 1;
}

void allocate()
{
    // 输入进程的size大小
    cout << "\nEnter process size: ";
    int size;
    cin >> size;

    // 遍历所有空闲分区
    for (int i = 0; i < numFreePartitions; i++)
    {
        if (!partitionAllocated[i] && partitionSize[i] >= size)
        {
            partitionAllocated[i] = true;
            int remainingSize = partitionSize[i] - size;
            if (remainingSize > 1)
            { // 还有没分配完的内存
                for (int j = numFreePartitions; j > i + 1; j--)
                {
                    partitionStart[j] = partitionStart[j - 1];
                    partitionSize[j] = partitionSize[j - 1];
                    partitionAllocated[j] = partitionAllocated[j - 1];
                }
                partitionStart[i + 1] = partitionStart[i] + size;
                partitionSize[i + 1] = remainingSize;
                partitionAllocated[i + 1] = false;
                numFreePartitions++;
                partitionSize[i] = size;
            }
            cout << "Memory allocated successfully to process." << endl;
            return;
        }
    }
    cout << "Memory allocation failed. No free partition available." << endl;
}

void deallocate()
{
    cout << "\nEnter partition number to deallocate (starting from 0): ";
    int partitionNum;
    cin >> partitionNum;

    if (partitionNum < 0 || partitionNum >= numFreePartitions)
    { // 不符合规范的分区号
        cout << "Invalid partition number." << endl;
    }
    else if (!partitionAllocated[partitionNum])
    { // 分区已经空闲
        cout << "This partition is already free." << endl;
    }
    else
    {
        partitionAllocated[partitionNum] = false;
        // 合并相邻的。此处应用链表更合适

        // 合并前一个
        if (partitionNum > 0 && !partitionAllocated[partitionNum - 1])
        {
            partitionSize[partitionNum - 1] += partitionSize[partitionNum];
            for (int i = partitionNum; i < numFreePartitions - 1; i++)
            {
                partitionStart[i] = partitionStart[i + 1];
                partitionSize[i] = partitionSize[i + 1];
                partitionAllocated[i] = partitionAllocated[i + 1];
            }
            numFreePartitions--;
            partitionNum--; // 已经合并了，需要调整一下块号
        }

        // 合并后一个

        if (partitionNum < numFreePartitions - 1 && !partitionAllocated[partitionNum + 1])
        {
            partitionSize[partitionNum] += partitionSize[partitionNum + 1];
            for (int i = partitionNum + 1; i < numFreePartitions - 1; i++)
            {
                partitionStart[i] = partitionStart[i + 1];
                partitionSize[i] = partitionSize[i + 1];
                partitionAllocated[i] = partitionAllocated[i + 1];
            }
            numFreePartitions--;
        }
        cout << "Memory deallocated successfully." << endl;
    }
}

void display()
{
    if (numFreePartitions == 0)
    {
        cout << "All memory is allocated." << endl;
    }
    else
    {
        cout << "\nPartition\tStart Address\tSize(MB)\tAllocated" << endl;
        for (int i = 0; i < numFreePartitions; i++)
        {
            cout << i << "\t\t" << partitionStart[i] << "\t\t" << partitionSize[i] << "\t\t" << partitionAllocated[i] << endl;
        }
    }
}

int main()
{
    init();
    int option;

    do
    {
        cout << "\nEnter your option:" << endl
             << "1. Allocate memory" << endl
             << "2. Deallocate memory" << endl
             << "3. Display partitions" << endl
             << "4. Exit" << endl;
        cin >> option;
        switch (option)
        {
        // 分配内存
        case 1:
            allocate();
            break;
        // 回收内存
        case 2:
            deallocate();
            break;
        // 展示分区
        case 3:
            display();
            break;
        // 退出程序
        case 4:
            return 0;
        default:
            cout << "Invalid option" << endl;
            break;
        }
    } while (option != 4);

    return 0;
}